package 单向无头链表;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: MENG
 * Date: 2022-07-03
 * Time: 21:59
 */
class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }


}
public class TestSingleList {
    public ListNode head;

    //无头的模拟实现插入元素，其实是用头插和尾插法，不是这种方法
    public void creatList() {
        ListNode node1 = new ListNode(10);
        ListNode node2 = new ListNode(12);
        ListNode node3 = new ListNode(23);
        ListNode node4 = new ListNode(34);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;
    }

    public void disPlay() {
        ListNode cur = this.head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }


        public void disPlay(ListNode head1){
            ListNode cur = head1.next;
            while(cur != null){
                System.out.print(cur.val+" ");
                cur = cur.next;
            }

        }
    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
        } else {
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    public void checkIndex(int index) {
        if (index < 0 || index > size()) {
            throw new IndexNotLegalException("Index位置不合法");
        }
    }

    //得到单链表的长度
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }



    //找到index的前一个节点
    private ListNode findPreIndex(int index){
        ListNode cur = head;
        while(index - 1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标，先检查下标的合法性
    public void addIndex(int index,int data){
        checkIndex(index);
        if(index == 0){
            addFirst(data);
            return;
        } else if(index == size()){
            addLast(data);
            return;
        }else{
            ListNode node = new ListNode(data);
            ListNode preIndex = findPreIndex(index);
            //这两局代码不能反过来（补充笔记）
            node.next = preIndex.next;
            preIndex.next = node;
        }
    }

    //找到key的前一个节点
    private ListNode searchPreOfKey(int key){
        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    //删除第一个出现的key
    public void remove(int key){
        if(head.val == key){
            head = head.next;
            return;
        }
        ListNode cur = searchPreOfKey(key);
        if(cur == null){
            return;
        }
        ListNode del = cur.next;//要删除的节点
        cur.next = del.next;
//        cur.next = cur.next.next;//另一种写法
    }


    //删除所有的key
    public void removeAll(int key) {
        //第一种方法
        if (head != null) {
            ListNode pre = this.head;
            ListNode cur = this.head.next;
            while (cur != null) {
                if (cur.val == key) {
                    pre.next = cur.next;
                    cur = cur.next;
                } else {
                    pre = cur;
                    cur = cur.next;
                }
            }
            if (head.val == key) {
                head = head.next;
            }

        }
        if (head == null) {
            return;
        }
    }
    /*//第二种方法，创建虚拟头结点(返回值是创建的有虚拟结点的数组)
    public Node removeAll(int key) {
        Node dummHead = new Node(0);
        dummHead.next = head;


        if (head == null) {
            return null;
        }
        if (head != null) {

            Node prev = dummHead;
            Node cur = dummHead.next;
            while (cur != null) {
                if (cur.val == key) {
                    prev.next = cur.next;
                    cur = cur.next;
                } else {
                    prev = cur;
                    cur = cur.next;
                }
            }

        }
        return dummHead;
    }*/

    public void clear(int a ) {
        this.head = null;
    }


    //面试题
    //反转一个单链表
    public ListNode reverseList(){
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    //给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
    public ListNode middleNode(){
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    //输入一个链表，输出该链表中倒数第k个结点
    public ListNode findKthToTail(int k){
        //k合理性判断，因为只遍历一遍，所以k>size()用另一种方式实现
        ListNode fast = head;
        ListNode slow = head;
        if(k <= 0 || head == null){
            return null;
        }
        while(k-1 != 0){
            fast = fast.next;
            if(fast == null){
                return null;
            }
            k--;
        }
        while(fast.next != null){
            //用fast.next那么fast就先走k-1步，用fast!=null，那么就走k步
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    //编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
    public ListNode partition(int x) {
        ListNode bs = null;
        ListNode be = null;

        ListNode as = null;
        ListNode ae = null;
        ListNode cur = head;
        while(cur != null){
            //插入到左侧b这边
            if(cur.val < x){
                //第一次插入元素
                if(bs == null){
                    bs = cur;
                    be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
                //cur.val > x，放到a这侧
            }else{
                if(as == null){
                    as = cur;
                    ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }

            }
            cur = cur.next;

        }
        //判断前半部分是否有节点
        if(bs == null){
            return as;
        }
        //前半部分b和后半部分a连接，判断a中是否有节点，如果有节点，是要把后半部分a的最后一个节点，让他是null结尾即可。
        be.next = as;
        if(as != null){
            ae.next = null;
        }
        return bs;
    }

    //链表的回文结构
    public boolean chkPalindrome(){
        if(head == null){
            return true;
        }
        //寻找中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //翻转中间节点的后半部分
        ListNode cur = slow.next;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //开始回文
        //两个指针，一个head从前遍历，一个slow从后遍历(是翻转之后的头节点)
        while(head != slow){
            if(head.val != slow.val){
                return false;
            }
            //判断节点是偶数的个数，如果满足下面条件，且不再上述代码中，那就返回true
            if(head.next == slow){
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;


    }
    //给定一个链表，判断链表中是否有环。
    public boolean hasCycle(){
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return false;
        }
        return true;
    }

    //给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL
    public ListNode detectCycle(){
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;
        }
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;

    }

}